package algorithm.recursionAndbacktrack.p52;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 52. N皇后 II
 */
class Solution {
    private boolean[] col_Occupied, diag1_Occupied, diag2_Occupied;
    private int count = 0;
    public int totalNQueens(int n) {
        col_Occupied = new boolean[n];
        diag1_Occupied = new boolean[2 * n - 1];
        diag2_Occupied = new boolean[2 * n - 1];
        putQueen(n, new ArrayDeque<String>());
        return count;
    }

    private void putQueen(int n, Deque<String> result) {
        int rowIndex = result.size();
        if (rowIndex == n) {
            count ++;
            return;
        }

        // 放在哪一列
        for (int i = 0; i < n; i++) {
            // 在这一行的这一列放下会不会跟其他皇后冲突
            if(col_Occupied[i] || diag1_Occupied[rowIndex + i] || diag2_Occupied[rowIndex - i + n - 1])
                continue;
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if (j == i) {
                    sb.append('Q');
                } else sb.append('.');
            }
            // 添加N皇后一个解的一行
            result.addLast(sb.toString());
            // 将这个皇后摆放位置的列和两个对角线都占住
            col_Occupied[i] = true;
            diag1_Occupied[rowIndex + i] = true;
            diag2_Occupied[rowIndex - i + n - 1] = true;
            putQueen(n, result);

            // 状态回溯
            diag2_Occupied[rowIndex - i + n - 1] = false;
            diag1_Occupied[rowIndex + i] = false;
            col_Occupied[i] = false;
            // 去掉解的这最近一行
            result.removeLast();
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().totalNQueens(4));
    }

}